int **res;
int *path;
int pathlen, res_size;
int sum;

// 组合总和1：
// 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
// candidates 中的数字可以无限制重复被选取。

// 输入：candidates = [2,3,6,7], target = 7,
// 所求解集为：
// [
//   [7],
//   [2,2,3]
// ]


//类似0-1背包，累加和超过target就回溯并减去当前值，并排除掉组合问题的重复情况
void backtrace(int start, int* arr, int len, int target, int** returnColumnSizes) {
    if (sum > target) return;
    if (sum == target) {
            // printf("pathlen:%d\n", pathlen);
            // for (int j = 0; j < pathlen; j++) printf("%d ", path[j]);
            // printf("\n");

            //保存解
            res[res_size] = malloc(sizeof(int) * pathlen);
            memcpy(res[res_size], path, sizeof(int)*pathlen);
            (*returnColumnSizes)[res_size] = pathlen;
            res_size++;
            return ;
    }
    for (int i = start; i < len; i++) { // 组合问题，for中起始用start，前面的已经选过了
        sum += arr[i];
        path[pathlen++] = arr[i];
        backtrace(i, arr, len, target, returnColumnSizes);  //可以重复选arr[i]，所以不用i+1
        sum -= arr[i];
        pathlen--;
    }
}

int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes){
    res = malloc(sizeof(int *) * 1001);
    *returnColumnSizes = malloc(sizeof(int)*1001);
    path = malloc(sizeof(int) * 2001);
    pathlen = 0; res_size = 0; sum = 0;
    backtrace(0, candidates, candidatesSize, target, returnColumnSizes);

    *returnSize = res_size;
	free(path);
    return res;
}


// 组合总和2：
//给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//candidates 中的每个数字在每个组合中只能使用一次。

    // 所有数字（包括目标数）都是正整数。
    // 解集不能包含重复的组合。 

// 输入: candidates = [10,1,2,7,6,1,5], target = 8,
// 所求解集为:
// [
//   [1, 7],
//   [1, 2, 5],
//   [2, 6],
//   [1, 1, 6]
// ]


// 每个数字只能使用一次，则纵向遍历时backtrace(i+1, , , ,);
// 不能包含重复组合，而数组中有重复元素；则排序+used，树的同一层中，数值只能使用一次
// if (i > 0 && arr[i] == arr[i-1] && !used[i-1]) continue;



